package demo_leetcode_day;

/*
给定一组唯一的单词， 找出所有不同 的索引对(i, j)，使得列表中的两个单词， words[i] + words[j] ，可拼接成回文串。

示例 1:

输入: ["abcd","dcba","lls","s","sssll"]
输出: [[0,1],[1,0],[3,2],[2,4]]
解释: 可拼接成的回文串为 ["dcbaabcd","abcddcba","slls","llssssll"]
示例 2:

输入: ["bat","tab","cat"]
输出: [[0,1],[1,0]]
解释: 可拼接成的回文串为 ["battab","tabbat"]
*/

import java.util.ArrayList;
import java.util.List;

public class demo_20200806 {
    public static void main(String[] args) {
        System.out.println(new Solution().palindromePairs(new String[]{"abcd","dcba","lls","s","sssll"}));
    }

    static class Solution {
        public List<List<Integer>> palindromePairs(String[] words) {
            List<List<Integer>> ret = new ArrayList<>();

            int size = words.length;
            for (int i = 0; i < size - 1; i++) {
                for (int j = i + 1; j < size; j++) {
                    // 两组是否是可以组合成回文
                    isPalindromic(words, i, j, ret);
                    isPalindromic(words, j, i, ret);
                }
            }
            return ret;
        }

        // 判断是否是回文
        private void isPalindromic(String[] words, int i, int j, List<List<Integer>> ret) {
            String leftWord = words[i];
            String rightWord = words[j];
            int left = 0;
            int right = rightWord.length() - 1;
            int min = Math.min(leftWord.length(), rightWord.length());
            // 遍历处理
            while (left <= right + leftWord.length()) {
                // 在各自字符串里
                if (left < min) {
                    if (leftWord.charAt(left) != rightWord.charAt(right)) {
                        return;
                    }
                } else {
                    if(leftWord.length() == min){
                        if (rightWord.charAt(left - min) != rightWord.charAt(right)) {
                            return;
                        }
                    }else {
                        if (leftWord.charAt(left) != leftWord.charAt(right + leftWord.length())) {
                            return;
                        }
                    }
                }
                left++;
                right--;
            }
            // 成功，追加
            List<Integer> list = new ArrayList<>();
            list.add(i);
            list.add(j);
            ret.add(list);
        }
    }
}
